{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path With Maximum Minimum Value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumMinimumPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得分最高的路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>m x n</code> 的整数矩阵&nbsp;<code>grid</code>，返回从 <code>(0,0)</code> 开始到 <code>(m - 1, n - 1)</code> 在四个基本方向上移动的路径的最大 <strong>分数</strong> 。</p>\n",
    "\n",
    "<p>一条路径的 <strong>分数</strong> 是该路径上的最小值。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，路径 <code>8 → 4 → 5 → 9</code> 的得分为 <code>4</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/05/maxgrid1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[5,4,5],[1,2,6],[7,4,6]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>得分最高的路径用黄色突出显示。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/05/maxgrid2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]\n",
    "<strong>输出：</strong>2</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/08/05/maxgrid3.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]\n",
    "<strong>输出：</strong>3</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-with-maximum-minimum-value](https://leetcode.cn/problems/path-with-maximum-minimum-value/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-with-maximum-minimum-value](https://leetcode.cn/problems/path-with-maximum-minimum-value/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[5,4,5],[1,2,6],[7,4,6]]', '[[2,2,1,2,2,2],[1,2,2,2,1,2]]', '[[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, x) -> None:\n",
    "        self.uf = [-1] * x\n",
    "\n",
    "    def find(self, x):\n",
    "        r = x\n",
    "        while self.uf[x] >= 0:\n",
    "            x = self.uf[x]\n",
    "\n",
    "        while r != x:\n",
    "            self.uf[r], r = x, self.uf[r]\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        ux, uy = self.find(x), self.find(y)\n",
    "        if ux == uy:\n",
    "            return\n",
    "        if self.uf[ux] >= self.uf[uy]:\n",
    "            self.uf[uy] += self.uf[ux]\n",
    "            self.uf[ux] = uy\n",
    "        else:\n",
    "            self.uf[ux] += self.uf[uy]\n",
    "            self.uf[uy] = ux\n",
    "        return\n",
    "\n",
    "    def count(self):\n",
    "        ans = 0\n",
    "        for c in self.uf:\n",
    "            if c < 0 and c != -1:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "    def valid(self):\n",
    "        n = len(self.uf)\n",
    "        for c in range(n):\n",
    "            if self.uf[c] == -n:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def __print__(self):\n",
    "        return self.uf\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        l,r = 0,min(grid[0][0],grid[n - 1][m - 1])\n",
    "        def check(x):\n",
    "            uf = UnionFind(n * m)\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if grid[i][j] < x:\n",
    "                        continue\n",
    "                    for dx,dy in [(-1,0),(0,-1)]:\n",
    "                        nx,ny = i + dx,j + dy\n",
    "                        if nx < n and nx >= 0 and ny < m  and ny >= 0 and grid[nx][ny] >= x:\n",
    "                            uf.union(i * m + j,nx * m + ny)\n",
    "            return uf.find(0) == uf.find(n * m - 1)\n",
    "        \n",
    "        \n",
    "        \n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        # def find(node):\n",
    "        #     # print('node:', node)\n",
    "        #     # print('parent',len(parent))\n",
    "        #     if parent[node] != node:\n",
    "        #         parent[node] = find(parent[node])\n",
    "        #     return parent[node]\n",
    "        # def union(node1,node2):\n",
    "        #     # print(find(node2))\n",
    "        #     # print(node2)\n",
    "        #     # print(len(parent))\n",
    "        #     parent[find(node1)] = find(node2)\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "        # # print('RRRRRR',R)\n",
    "        # # print('CCCCCC',C)\n",
    "        # vals = [[row,col] for row in range(R) for col in range(C)]\n",
    "        # vals.sort(key = lambda x: grid[x[0]][x[1]], reverse = True)\n",
    "\n",
    "        # parent = list(range(R*C))\n",
    "        # original_min = min(grid[0][0],grid[R-1][C-1])\n",
    "        # visited = [[0]*C for _ in range(R)]\n",
    "\n",
    "        # for i in range(len(vals)):\n",
    "        #     if grid[vals[i][0]][vals[i][1]]>=original_min:\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 # print('vals[i][1]*C+vals[i][1]',vals[i][1]*C+vals[i][1])\n",
    "        #                 # print(vals[i][0]+x)\n",
    "        #                 # print(vals[i][1]+y)\n",
    "        #                 # print(R)\n",
    "        #                 # print(C)\n",
    "        #                 # print('(vals[i][1]+x)*C+vals[i][1]+y',(vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return original_min\n",
    "        #     elif  grid[vals[i][0]][vals[i][1]]<original_min:\n",
    "        #         # print('parent',parent)\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return grid[vals[i][0]][vals[i][1]]\n",
    "\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "        dirs = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        def path_exists(cur_score):\n",
    "            dq = collections.deque()\n",
    "            visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "            dq.append([0,0])\n",
    "            visited[0][0] = True\n",
    "\n",
    "            while dq:\n",
    "                cur_row, cur_col = dq.popleft()\n",
    "\n",
    "                if cur_row == R-1 and cur_col==C-1:\n",
    "                    return True\n",
    "                for d_row, d_col in dirs:\n",
    "                    new_row = cur_row + d_row\n",
    "                    new_col = cur_col + d_col\n",
    "\n",
    "                    if not(0<=new_row<R and 0<=new_col<C):\n",
    "                        continue\n",
    "                    if grid[new_row][new_col] >= cur_score and not visited[new_row][new_col]:\n",
    "                        visited[new_row][new_col] = True\n",
    "                        dq.append([new_row,new_col])\n",
    "            return False\n",
    "       \n",
    "        left = 0\n",
    "        right = min(grid[0][0],grid[-1][-1])\n",
    "\n",
    "        while left< right:\n",
    "            middle = (left+right+1)//2\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle-1\n",
    "\n",
    "        return left    \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        qu=deque()               #定义一个队列,元素为[x,y,length]\n",
    "        qu.append([0,0,grid[0][0]])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        while qu:\n",
    "            [x,y,length]=qu.popleft()       #出队元素\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlength=min(dist[x][y],grid[nx][ny])\n",
    "                if curlength>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlength\n",
    "                    qu.append([nx,ny,dist[nx][ny]])\n",
    "        return dist[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        pqu=[]                          #定义大根堆pqu,元素为[-length,x,y]\n",
    "        heapq.heappush(pqu,[-grid[0][0],0,0])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            length,x,y=e[0],e[1],e[2]\n",
    "            length=-length              #恢复正值\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlength=min(dist[x][y],grid[nx][ny])\n",
    "                if curlength>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlength\n",
    "                    heapq.heappush(pqu,[-dist[nx][ny],nx,ny])\n",
    "        return dist[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        pqu=[]                          #定义大根堆pqu,元素为[-length,x,y]\n",
    "        heapq.heappush(pqu,[-grid[0][0],0,0])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            length,x,y=e[0],e[1],e[2]\n",
    "            length=-length              #恢复正值\n",
    "            if x==m-1 and y==n-1:return length\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlen=min(dist[x][y],grid[nx][ny])\n",
    "                if curlen>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlen\n",
    "                    heapq.heappush(pqu,[-dist[nx][ny],nx,ny])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        pqu=[]                          #定义大根堆pqu,元素为[-length,x,y]\n",
    "        heapq.heappush(pqu,[-grid[0][0],0,0])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            length,x,y=e[0],e[1],e[2]\n",
    "            length=-length              #恢复正值\n",
    "            #if x==m-1 and y==n-1:return length\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlength=min(dist[x][y],grid[nx][ny])\n",
    "                if curlength>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlength\n",
    "                    heapq.heappush(pqu,[-dist[nx][ny],nx,ny])\n",
    "        return dist[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        pqu=[]                          #定义大根堆pqu,元素为[-length,x,y]\n",
    "        heapq.heappush(pqu,[-grid[0][0],0,0])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            length,x,y=e[0],e[1],e[2]\n",
    "            length=-length              #恢复正值\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlength=min(dist[x][y],grid[nx][ny])\n",
    "                if curlength>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlength\n",
    "                    heapq.heappush(pqu,[-dist[nx][ny],nx,ny])\n",
    "        return dist[m-1][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        dx=[0,0,1,-1]                       #水平方向偏移量\n",
    "        dy=[1,-1,0,0]                   #垂直方向偏移量\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dist=[[-1 for _ in range(0,n)] for _ in range(0,m)]\n",
    "        pqu=[]                          #定义大根堆pqu,元素为[-length,x,y]\n",
    "        heapq.heappush(pqu,[-grid[0][0],0,0])      #源点元素进队\n",
    "        dist[0][0]=grid[0][0]\n",
    "        ans=0\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            length,x,y=e[0],e[1],e[2]\n",
    "            length=-length              #恢复正值\n",
    "            if x==m-1 and y==n-1:ans=max(ans,length)\n",
    "            for di in range(0,4):\n",
    "                nx,ny=x+dx[di],y+dy[di]\n",
    "                if nx<0 or nx>=m or ny<0 or ny>=n:continue\n",
    "                curlength=min(dist[x][y],grid[nx][ny])\n",
    "                if curlength>dist[nx][ny]:\n",
    "                    dist[nx][ny]=curlength\n",
    "                    heapq.heappush(pqu,[-dist[nx][ny],nx,ny])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        \n",
    "        def check(x):\n",
    "            uf = UnionFind(m*n)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] >= x:\n",
    "                        for a, b in [[i+1, j], [i, j+1]]:\n",
    "                            if 0<=a<m and 0<=b<n and grid[a][b] >= x:\n",
    "                                uf.union(i*n+j, a*n+b)\n",
    "            return uf.is_connected(0, m*n-1)\n",
    "        \n",
    "        return BinarySearch().find_int_right(0, grid[0][0], check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        # def find(node):\n",
    "        #     # print('node:', node)\n",
    "        #     # print('parent',len(parent))\n",
    "        #     if parent[node] != node:\n",
    "        #         parent[node] = find(parent[node])\n",
    "        #     return parent[node]\n",
    "        # def union(node1,node2):\n",
    "        #     # print(find(node2))\n",
    "        #     # print(node2)\n",
    "        #     # print(len(parent))\n",
    "        #     parent[find(node1)] = find(node2)\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "        # # print('RRRRRR',R)\n",
    "        # # print('CCCCCC',C)\n",
    "        # vals = [[row,col] for row in range(R) for col in range(C)]\n",
    "        # vals.sort(key = lambda x: grid[x[0]][x[1]], reverse = True)\n",
    "\n",
    "        # parent = list(range(R*C))\n",
    "        # original_min = min(grid[0][0],grid[R-1][C-1])\n",
    "        # visited = [[0]*C for _ in range(R)]\n",
    "\n",
    "        # for i in range(len(vals)):\n",
    "        #     if grid[vals[i][0]][vals[i][1]]>=original_min:\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 # print('vals[i][1]*C+vals[i][1]',vals[i][1]*C+vals[i][1])\n",
    "        #                 # print(vals[i][0]+x)\n",
    "        #                 # print(vals[i][1]+y)\n",
    "        #                 # print(R)\n",
    "        #                 # print(C)\n",
    "        #                 # print('(vals[i][1]+x)*C+vals[i][1]+y',(vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return original_min\n",
    "        #     elif  grid[vals[i][0]][vals[i][1]]<original_min:\n",
    "        #         # print('parent',parent)\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return grid[vals[i][0]][vals[i][1]]\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "        # dirs = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        # def path_exists(cur_score):\n",
    "        #     dq = collections.deque()\n",
    "        #     visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "        #     dq.append([0,0])\n",
    "        #     visited[0][0] = True\n",
    "\n",
    "        #     while dq:\n",
    "        #         cur_row, cur_col = dq.popleft()\n",
    "\n",
    "        #         if cur_row == R-1 and cur_col==C-1:\n",
    "        #             return True\n",
    "        #         for d_row, d_col in dirs:\n",
    "        #             new_row = cur_row + d_row\n",
    "        #             new_col = cur_col + d_col\n",
    "\n",
    "        #             if not(0<=new_row<R and 0<=new_col<C):\n",
    "        #                 continue\n",
    "        #             if grid[new_row][new_col] >= cur_score and not visited[new_row][new_col]:\n",
    "        #                 visited[new_row][new_col] = True\n",
    "        #                 dq.append([new_row,new_col])\n",
    "        #     return False\n",
    "       \n",
    "        # left = 0\n",
    "        # right = min(grid[0][0],grid[-1][-1])\n",
    "\n",
    "        # while left< right:\n",
    "        #     middle = (left+right+1)//2\n",
    "        #     if path_exists(middle):\n",
    "        #         left = middle\n",
    "        #     else:\n",
    "        #         right = middle-1\n",
    "\n",
    "        # return left    \n",
    "\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "\n",
    "        # dirs = ([1,0],[-1,0],[0,1],[0,-1])\n",
    "\n",
    "        # def path_exists(val):\n",
    "        #     visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "        #     def dfs(cur_row, cur_col):\n",
    "        #         if cur_row == R-1 and cur_col == C-1:\n",
    "        #             return True\n",
    "                \n",
    "        #         visited[cur_row][cur_col] = True\n",
    "\n",
    "        #         for d_row, d_col in dirs:\n",
    "        #             new_row = cur_row + d_row\n",
    "        #             new_col = cur_col + d_col\n",
    "\n",
    "        #             if not (0<=new_row<R and 0<=new_col<C) or visited[new_row][new_col]:\n",
    "        #                 continue\n",
    "        #             if grid[new_row][new_col]>=val and dfs(new_row,new_col):\n",
    "        #                 return True\n",
    "        #         return False\n",
    "        #     return dfs(0,0)\n",
    "\n",
    "        # left = 0\n",
    "        # right = min(grid[0][0],grid[-1][-1])\n",
    "\n",
    "        # while left < right:\n",
    "        #     middle = (left+right+1)//2\n",
    "\n",
    "        #     if path_exists(middle):\n",
    "        #         left = middle\n",
    "        #     else:\n",
    "        #         right = middle-1\n",
    "        \n",
    "        # return left\n",
    "\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "\n",
    "        dirs = [[0,1],[0,-1],[-1,0],[1,0]]\n",
    "\n",
    "        heap = []\n",
    "        ans = grid[0][0]\n",
    "\n",
    "        visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "        heapq.heappush(heap,(-grid[0][0],0,0))\n",
    "\n",
    "        visited[0][0] = True\n",
    "\n",
    "        while heap:\n",
    "            cur_val, cur_row, cur_col = heapq.heappop(heap)\n",
    "\n",
    "            ans = min(ans, grid[cur_row][cur_col])\n",
    "\n",
    "            if cur_row == R-1 and cur_col==C-1:\n",
    "                break\n",
    "            for d_row, d_col in dirs:\n",
    "                new_row = cur_row + d_row\n",
    "                new_col = cur_col + d_col\n",
    "\n",
    "                if 0<=new_row<R and 0<=new_col<C and not visited[new_row][new_col]:\n",
    "                    heapq.heappush(heap, (-grid[new_row][new_col], new_row, new_col))\n",
    "                    visited[new_row][new_col] = True\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        nums = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] <= min(grid[0][0], grid[-1][-1]):\n",
    "                    nums.add(grid[i][j])\n",
    "        \n",
    "        aspect = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        def isgood(num):\n",
    "            finded = [[0 for _ in range(m)] for _ in range(n)]\n",
    "\n",
    "            de = deque([[0, 0]])\n",
    "            finded[0][0] = 1\n",
    "\n",
    "            while de:\n",
    "                x, y = de.pop()\n",
    "                for a, b in aspect:\n",
    "                    a += x\n",
    "                    b += y\n",
    "                    if 0 <= a < n and 0 <= b < m and grid[a][b] >= nums[num] and not finded[a][b]:\n",
    "                        finded[a][b] = 1\n",
    "                        de.appendleft((a, b))\n",
    "                        if (a, b) == (n - 1, m - 1):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        nums = sorted(list(nums))\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        if isgood(right):\n",
    "            return nums[right]\n",
    "        \n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if isgood(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return nums[right] if isgood(right) else nums[left] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        def path_exists(cur_score):\n",
    "            visited = set()\n",
    "            visited.add((0, 0))\n",
    "\n",
    "            dq = deque([(0, 0)])\n",
    "\n",
    "            while dq:\n",
    "                cur_x, cur_y = dq.popleft()\n",
    "\n",
    "                if cur_x == m -1 and cur_y == n - 1:\n",
    "                    return True\n",
    "                for dx, dy in dirs:\n",
    "                    new_x = cur_x + dx\n",
    "                    new_y  = cur_y + dy\n",
    "\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and (new_x, new_y) not in visited and grid[new_x][new_y] >= cur_score:\n",
    "                        visited.add((new_x, new_y))\n",
    "                        dq.append((new_x, new_y))\n",
    "\n",
    "            return False\n",
    "\n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1]) + 1\n",
    "        \n",
    "        while left + 1 < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        def path_exists(cur_score):\n",
    "            visited = set()\n",
    "            visited.add((0, 0))\n",
    "\n",
    "            dq = deque([(0, 0)])\n",
    "\n",
    "            while dq:\n",
    "                cur_x, cur_y = dq.popleft()\n",
    "\n",
    "                if cur_x == m -1 and cur_y == n - 1:\n",
    "                    return True\n",
    "                for dx, dy in dirs:\n",
    "                    new_x = cur_x + dx\n",
    "                    new_y  = cur_y + dy\n",
    "\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and (new_x, new_y) not in visited and grid[new_x][new_y] >= cur_score:\n",
    "                        visited.add((new_x, new_y))\n",
    "                        dq.append((new_x, new_y))\n",
    "\n",
    "            return False\n",
    "\n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1]) + 1\n",
    "        \n",
    "        while left + 1 < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        h = [[-grid[0][0], 0, 0]]\n",
    "        visited = {(0, 0)}\n",
    "        dist = [[-float('inf')] * n for _ in range(m)]\n",
    "        dist[0][0] = grid[0][0]\n",
    "        while h:\n",
    "            rscore, x, y = heappop(h)\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return -rscore\n",
    "            visited.add((x, y))\n",
    "            for i, j in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:\n",
    "                if 0 <= i < m and 0 <= j < n and (i, j) not in visited:\n",
    "                    d = min(-rscore, grid[i][j])\n",
    "                    if d > dist[i][j]:\n",
    "                        dist[i][j] = d\n",
    "                        heappush(h, [-d, i, j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        def path_exists(cur_score):\n",
    "            visited = set()\n",
    "            visited.add((0, 0))\n",
    "\n",
    "            dq = deque([(0, 0)])\n",
    "\n",
    "            while dq:\n",
    "                cur_x, cur_y = dq.popleft()\n",
    "\n",
    "                if cur_x == m -1 and cur_y == n - 1:\n",
    "                    return True\n",
    "                for dx, dy in dirs:\n",
    "                    new_x = cur_x + dx\n",
    "                    new_y  = cur_y + dy\n",
    "\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and (new_x, new_y) not in visited and grid[new_x][new_y] >= cur_score:\n",
    "                        visited.add((new_x, new_y))\n",
    "                        dq.append((new_x, new_y))\n",
    "\n",
    "            return False\n",
    "\n",
    "        left = -1\n",
    "        right = min(grid[0][0], grid[-1][-1]) + 1\n",
    "        \n",
    "        while left + 1 < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution(object):\n",
    "    def maximumMinimumPath(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        if not A or not A[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(A), len(A[0])\n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        \n",
    "        queue = [[-A[0][0], 0, 0]] #Python默认最小堆，因此需要手动用相反数实现最大堆……\n",
    "        visited = set([0,0])\n",
    "        heapify(queue)\n",
    "\n",
    "        while queue:\n",
    "            score, x0, y0 = heappop(queue) #把目前队里最优的点找出来，三个值分别代表分数， X坐标， Y坐标\n",
    "            if [x0, y0] == [m - 1, n - 1]: #如果已经到终点了\n",
    "                return -score #输出结果时记得再取一次相反数\n",
    "            \n",
    "            for k in range(4): #找四个可能的邻居点\n",
    "                x = x0 + dx[k]\n",
    "                y = y0 + dy[k]\n",
    "                \n",
    "                if 0 <= x < m and 0 <= y < n and (x, y) not in visited:#邻居点可走\n",
    "                    visited.add((x, y))\n",
    "                    heappush(queue, [max(score, -A[x][y]), x, y]) #邻居点入队，调整分数，因为取了相反数所以找最小值用max不用min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路和心得：\n",
    "# 1.涉及到连通性问题，果断并查集\n",
    "# 2.二维坐标映射成唯一ID\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for x in range(n)]\n",
    "        self.part = n\n",
    "    #----------- 扁平化\n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    #---------- size策略\n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.part -= 1\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "    def get_part_size(self, x: int) -> int:\n",
    "        root_x = self.Find(x)\n",
    "        return self.size[root_x] \n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, A: List[List[int]]) -> int:\n",
    "        Row, Col = len(A), len(A[0])\n",
    "        n = Row * Col\n",
    "        UF = UnionFind(n)\n",
    "        a = []\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                a.append((A[r][c], r, c))\n",
    "        a.sort() \n",
    "        #----------------- 并查集--check连通性\n",
    "        res = min(A[0][0], A[Row-1][Col-1])     #因为在运算过程中，这两个点的val没有与res比较\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        visited.add(n - 1)\n",
    "        while UF.connected(0, n - 1) == False:\n",
    "            cost, r, c = a.pop(-1)\n",
    "            ID = r * Col + c\n",
    "            res = min(res, cost)\n",
    "            visited.add(ID)\n",
    "            #----------- 4个方向 在visited里，就可以Union\n",
    "            for dr,dc in [(-1, 0), (0,1), (1,0), (0,-1)]:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < Row and 0 <= nc < Col:\n",
    "                    nxt_ID = nr * Col + nc\n",
    "                    if nxt_ID in visited:\n",
    "                        UF.Union(ID, nxt_ID)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU(object):\n",
    "    def __init__(self, n):\n",
    "        self.par = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.par[x] != x:\n",
    "            self.par[x] = self.find(self.par[x])\n",
    "        return self.par[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        xr, yr = self.find(x), self.find(y)\n",
    "        if xr == yr:\n",
    "            return\n",
    "        if self.sz[xr] < self.sz[yr]:\n",
    "            xr, yr = yr, xr\n",
    "        self.par[yr] = xr\n",
    "        self.sz[xr] += self.sz[yr]\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, A: List[List[int]]) -> int:\n",
    "        R = len(A)\n",
    "        C = len(A[0])\n",
    "        n = R * C\n",
    "        d = DSU(n)\n",
    "        s = set()\n",
    "        points = []\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                points.append((A[i][j], i, j))\n",
    "        points.sort()\n",
    "        ans = min(A[0][0], A[R - 1][C - 1])\n",
    "        s.add((0, 0))\n",
    "        s.add((R - 1, C - 1))\n",
    "        while d.find(0) != d.find(n - 1):\n",
    "            p, x, y = points.pop()\n",
    "            ans = min(ans, p)\n",
    "            for i, j in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:\n",
    "                if (i, j) in s:\n",
    "                    d.union(x * C + y, i * C + j)\n",
    "                s.add((x, y))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.sz = [1] * n\n",
    "        self.n_comp = n\n",
    "    def find(self,x):\n",
    "        if x!=self.fa[x]:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x] < self.sz[y]:\n",
    "            y,x = x,y\n",
    "        self.fa[y] = x\n",
    "        self.sz[x] + self.sz[y]\n",
    "        self.n_comp -= 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        uf = UF(m*n)\n",
    "        def f(x,y):\n",
    "            return x*n+y\n",
    "\n",
    "        ans =min(grid[0][0],grid[m-1][n-1])\n",
    "\n",
    "        li = sorted([(x,y,c) for x,row in enumerate(grid) for y,c in enumerate(row)],key=lambda x:-x[2])\n",
    "        vis = set()\n",
    "        vis.add((m-1,n-1))\n",
    "        vis.add((0,0))\n",
    "        # uf.union(f(0,0),f(m-1,n-1))\n",
    "        while uf.find(f(0,0))!= uf.find(f(m-1,n-1)):\n",
    "            x,y,c = li.pop(0)\n",
    "            for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if x<0 or x>=m or y<0 or y>=n:\n",
    "                    continue\n",
    "                if (nx,ny) in vis:\n",
    "                    uf.union(f(nx,ny),f(x,y))\n",
    "            vis.add((x,y))\n",
    "            ans = min(ans,c)\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        def find(node):\n",
    "            # print('node:', node)\n",
    "            # print('parent',len(parent))\n",
    "            if parent[node] != node:\n",
    "                parent[node] = find(parent[node])\n",
    "            return parent[node]\n",
    "        def union(node1,node2):\n",
    "            # print(find(node2))\n",
    "            # print(node2)\n",
    "            # print(len(parent))\n",
    "            parent[find(node1)] = find(node2)\n",
    "\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "        # print('RRRRRR',R)\n",
    "        # print('CCCCCC',C)\n",
    "        vals = [[row,col] for row in range(R) for col in range(C)]\n",
    "        vals.sort(key = lambda x: grid[x[0]][x[1]], reverse = True)\n",
    "\n",
    "        parent = list(range(R*C))\n",
    "        original_min = min(grid[0][0],grid[R-1][C-1])\n",
    "        visited = [[0]*C for _ in range(R)]\n",
    "\n",
    "        for i in range(len(vals)):\n",
    "            if grid[vals[i][0]][vals[i][1]]>=original_min:\n",
    "                visited[vals[i][0]][vals[i][1]] = 1\n",
    "                for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                    if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "                        # print('vals[i][1]*C+vals[i][1]',vals[i][1]*C+vals[i][1])\n",
    "                        # print(vals[i][0]+x)\n",
    "                        # print(vals[i][1]+y)\n",
    "                        # print(R)\n",
    "                        # print(C)\n",
    "                        # print('(vals[i][1]+x)*C+vals[i][1]+y',(vals[i][0]+x)*C+vals[i][1]+y)\n",
    "                        union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "                if find(0)==find(R*C-1):\n",
    "                    return original_min\n",
    "            elif  grid[vals[i][0]][vals[i][1]]<original_min:\n",
    "                # print('parent',parent)\n",
    "                visited[vals[i][0]][vals[i][1]] = 1\n",
    "                for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "                    if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "                        union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "                if find(0)==find(R*C-1):\n",
    "                    return grid[vals[i][0]][vals[i][1]]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                g[grid[i][j]].append((i,j))\n",
    "        pa=list(range(m*n))\n",
    "        def find(k):\n",
    "            if pa[k]!=k:\n",
    "                pa[k]=find(pa[k])\n",
    "            return pa[k]\n",
    "        def union(x,y):\n",
    "            pa[find(y)]=find(x)\n",
    "        def isCon():\n",
    "            return find(0)==find(m*n-1)\n",
    "        c=set()\n",
    "        for lit in sorted(g.keys())[::-1]:\n",
    "            for x,y in g[lit]:\n",
    "                for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:\n",
    "                    if (nx,ny) in c:\n",
    "                        union(x*n+y,nx*n+ny)\n",
    "                c.add((x,y))\n",
    "            if isCon():return lit\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        # def find(node):\n",
    "        #     # print('node:', node)\n",
    "        #     # print('parent',len(parent))\n",
    "        #     if parent[node] != node:\n",
    "        #         parent[node] = find(parent[node])\n",
    "        #     return parent[node]\n",
    "        # def union(node1,node2):\n",
    "        #     # print(find(node2))\n",
    "        #     # print(node2)\n",
    "        #     # print(len(parent))\n",
    "        #     parent[find(node1)] = find(node2)\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "        # # print('RRRRRR',R)\n",
    "        # # print('CCCCCC',C)\n",
    "        # vals = [[row,col] for row in range(R) for col in range(C)]\n",
    "        # vals.sort(key = lambda x: grid[x[0]][x[1]], reverse = True)\n",
    "\n",
    "        # parent = list(range(R*C))\n",
    "        # original_min = min(grid[0][0],grid[R-1][C-1])\n",
    "        # visited = [[0]*C for _ in range(R)]\n",
    "\n",
    "        # for i in range(len(vals)):\n",
    "        #     if grid[vals[i][0]][vals[i][1]]>=original_min:\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 # print('vals[i][1]*C+vals[i][1]',vals[i][1]*C+vals[i][1])\n",
    "        #                 # print(vals[i][0]+x)\n",
    "        #                 # print(vals[i][1]+y)\n",
    "        #                 # print(R)\n",
    "        #                 # print(C)\n",
    "        #                 # print('(vals[i][1]+x)*C+vals[i][1]+y',(vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return original_min\n",
    "        #     elif  grid[vals[i][0]][vals[i][1]]<original_min:\n",
    "        #         # print('parent',parent)\n",
    "        #         visited[vals[i][0]][vals[i][1]] = 1\n",
    "        #         for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:\n",
    "        #             if 0<=vals[i][0]+x<R and 0<=vals[i][1]+y<C and visited[vals[i][0]+x][vals[i][1]+y]==1:\n",
    "        #                 union(vals[i][0]*C+vals[i][1], (vals[i][0]+x)*C+vals[i][1]+y)\n",
    "        #         if find(0)==find(R*C-1):\n",
    "        #             return grid[vals[i][0]][vals[i][1]]\n",
    "\n",
    "        # R = len(grid)\n",
    "        # C = len(grid[0])\n",
    "        # dirs = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        # def path_exists(cur_score):\n",
    "        #     dq = collections.deque()\n",
    "        #     visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "        #     dq.append([0,0])\n",
    "        #     visited[0][0] = True\n",
    "\n",
    "        #     while dq:\n",
    "        #         cur_row, cur_col = dq.popleft()\n",
    "\n",
    "        #         if cur_row == R-1 and cur_col==C-1:\n",
    "        #             return True\n",
    "        #         for d_row, d_col in dirs:\n",
    "        #             new_row = cur_row + d_row\n",
    "        #             new_col = cur_col + d_col\n",
    "\n",
    "        #             if not(0<=new_row<R and 0<=new_col<C):\n",
    "        #                 continue\n",
    "        #             if grid[new_row][new_col] >= cur_score and not visited[new_row][new_col]:\n",
    "        #                 visited[new_row][new_col] = True\n",
    "        #                 dq.append([new_row,new_col])\n",
    "        #     return False\n",
    "       \n",
    "        # left = 0\n",
    "        # right = min(grid[0][0],grid[-1][-1])\n",
    "\n",
    "        # while left< right:\n",
    "        #     middle = (left+right+1)//2\n",
    "        #     if path_exists(middle):\n",
    "        #         left = middle\n",
    "        #     else:\n",
    "        #         right = middle-1\n",
    "\n",
    "        # return left    \n",
    "\n",
    "\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "\n",
    "        dirs = ([1,0],[-1,0],[0,1],[0,-1])\n",
    "\n",
    "        def path_exists(val):\n",
    "            visited = [[False]*C for _ in range(R)]\n",
    "\n",
    "            def dfs(cur_row, cur_col):\n",
    "                if cur_row == R-1 and cur_col == C-1:\n",
    "                    return True\n",
    "                \n",
    "                visited[cur_row][cur_col] = True\n",
    "\n",
    "                for d_row, d_col in dirs:\n",
    "                    new_row = cur_row + d_row\n",
    "                    new_col = cur_col + d_col\n",
    "\n",
    "                    if not (0<=new_row<R and 0<=new_col<C) or visited[new_row][new_col]:\n",
    "                        continue\n",
    "                    if grid[new_row][new_col]>=val and dfs(new_row,new_col):\n",
    "                        return True\n",
    "                return False\n",
    "            return dfs(0,0)\n",
    "\n",
    "        left = 0\n",
    "        right = min(grid[0][0],grid[-1][-1])\n",
    "\n",
    "        while left < right:\n",
    "            middle = (left+right+1)//2\n",
    "\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle-1\n",
    "        \n",
    "        return left\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        \n",
    "        \n",
    "        def path_exists(val):\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    return True\n",
    "                vis[i][j]=1\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if 0<=x<m and 0<=y<n and (not vis[x][y]) and grid[x][y]>=k:\n",
    "                        if check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "        \n",
    "\n",
    "\n",
    "        l,r=0,min(grid[0][0], grid[-1][-1])\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            if path_exists(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        parents = list(range(m * n))\n",
    "        edges = list()\n",
    "        def find(index):\n",
    "            if parents[index] != index:\n",
    "                parents[index] = find(parents[index])\n",
    "            return parents[index]\n",
    "        def union(i, j):\n",
    "            parents[find(i)] = find(j)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                idx = i * n + j\n",
    "                if i > 0:\n",
    "                    edges.append((idx - n, idx, min(grid[i][j], grid[i-1][j])))\n",
    "                if j > 0:\n",
    "                    edges.append((idx - 1, idx, min(grid[i][j], grid[i][j-1])))\n",
    "        edges.sort(key=lambda x:-x[2])\n",
    "        res = 0\n",
    "        for edge in edges:\n",
    "            union(edge[0], edge[1])\n",
    "            if find(0) == find(m * n - 1):\n",
    "                res = edge[2]\n",
    "                break\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # 4 个指向单元格可能邻居的方向。\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # 确认我们能否找到一条路径的值等于 val\n",
    "        def path_exists(val):\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    return True\n",
    "                vis[i][j]=1\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if not (0<=x<m and 0<=y<n) or vis[x][y]:\n",
    "                        continue\n",
    "                    if grid[x][y]>=k and check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "                        \n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1])\n",
    " \n",
    "        while left < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right + 1) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        \n",
    "        # 一旦左右边界重合，我们就找到目标值，\n",
    "        # 即路径的最大值。\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vis=[[0]*n for _ in range(m)]\n",
    "        \n",
    "        \n",
    "        def check(i,j,k):\n",
    "            if i==0 and j==0 and grid[i][j]<k:\n",
    "                return False\n",
    "            if i==m-1 and j==n-1 and grid[i][j]>=k:\n",
    "                return True\n",
    "            vis[i][j]=1\n",
    "            for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                if 0<=x<m and 0<=y<n and (not vis[x][y]) and grid[x][y]>=k:\n",
    "                    if check(x, y, k):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        l,r=0,min(grid[0][0], grid[-1][-1])\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            if check(0, 0, mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        \n",
    "        \n",
    "        def path_exists(val):\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==0 and j==0 and grid[i][j]<k:\n",
    "                    return False\n",
    "                if i==m-1 and j==n-1 and grid[i][j]>=k:\n",
    "                    return True\n",
    "                vis[i][j]=1\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if 0<=x<m and 0<=y<n and (not vis[x][y]) and grid[x][y]>=k:\n",
    "                        if check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "        \n",
    "        l,r=0,min(grid[0][0], grid[-1][-1])\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            if path_exists(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        vis=[[0]*n for _ in range(m)]\n",
    "        \n",
    "        \n",
    "        def check(i,j,k):\n",
    "            if i==0 and j==0 and grid[i][j]<k:\n",
    "                return False\n",
    "            if i==m-1 and j==n-1 and grid[i][j]>=k:\n",
    "                return True\n",
    "            vis[i][j]=1\n",
    "            for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                if 0<=x<m and 0<=y<n and (not vis[x][y]) and grid[x][y]>=k:\n",
    "                    if check(x, y, k):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        l,r=0,max(grid[i][j] for i in range(m) for j in range(n))\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            if check(0, 0, mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        \n",
    "        \n",
    "        def path_exists(val):\n",
    "            vis=[[0]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    return True\n",
    "                vis[i][j]=1\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if not (0<=x<m and 0<=y<n) or vis[x][y]:\n",
    "                        continue\n",
    "                    if grid[x][y]>=k and check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "        \n",
    "\n",
    "\n",
    "        l,r=0,min(grid[0][0], grid[-1][-1])\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            if path_exists(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # 4 个指向单元格可能邻居的方向。\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # 确认我们能否找到一条路径的值等于 val\n",
    "        def path_exists(val):\n",
    "            vis=[[False]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    return True\n",
    "                vis[i][j]=True\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if not (0<=x<m and 0<=y<n) or vis[x][y]:\n",
    "                        continue\n",
    "                    if grid[x][y]>=k and check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "                        \n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1])\n",
    " \n",
    "        while left < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right + 1) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        \n",
    "        # 一旦左右边界重合，我们就找到目标值，\n",
    "        # 即路径的最大值。\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        # 二分答案 + DFS\n",
    "        direction = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        def dfs(x: int, y: int, limit: int) -> bool:\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return True\n",
    "            vis[x][y] = True\n",
    "            for dx, dy in direction:\n",
    "                new_x, new_y = x + dx, y + dy\n",
    "                if 0 <= new_x < m and 0 <= new_y < n:\n",
    "                    if vis[new_x][new_y] is False and grid[new_x][new_y] >= limit:\n",
    "                        if dfs(new_x, new_y, limit):\n",
    "                            return True\n",
    "            return False\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        left, right = 0, min(grid[0][0], grid[m - 1][n - 1])\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            vis = [[False] * n for _ in range(m)]\n",
    "            if dfs(0, 0, mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        R = len(grid)\n",
    "        C = len(grid[0])\n",
    "\n",
    "        # 4 个指向单元格可能邻居的方向。\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # 确认我们能否找到一条路径的值等于 val\n",
    "        def path_exists(val):\n",
    "            visited = [[False] * C for _ in range(R)]         \n",
    "            def dfs(cur_row, cur_col):\n",
    "                # 如果到达右下角的单元格，则返回 true。\n",
    "                if cur_row == R - 1 and cur_col == C - 1:\n",
    "                    return True\n",
    "\n",
    "                # 把当前的单元格标记为已访问。\n",
    "                visited[cur_row][cur_col] = True\n",
    "                for d_row, d_col in dirs:\n",
    "                    new_row = cur_row + d_row\n",
    "                    new_col = cur_col + d_col\n",
    "\n",
    "                    # 确保 (new_row, new_col) 在 grid 上并且还没有被访问\n",
    "                    if not (0 <= new_row < R and 0 <= new_col < C) or visited[new_row][new_col]:\n",
    "                        continue\n",
    "\n",
    "                    # 检查当前单元格是否有任何值\n",
    "                    # 大于或等于 val 的未访问邻居。\n",
    "                    if grid[new_row][new_col] >= val and dfs(new_row, new_col):\n",
    "                        # 如果是这样，我们就继续搜索这个邻居。\n",
    "                        return True\n",
    "                return False            \n",
    "            return dfs(0,0)   \n",
    "                        \n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1])\n",
    " \n",
    "        while left < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right + 1) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        \n",
    "        # 一旦左右边界重合，我们就找到目标值，\n",
    "        # 即路径的最大值。\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        # 4 个指向单元格可能邻居的方向。\n",
    "        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # 确认我们能否找到一条路径的值等于 val\n",
    "        def path_exists(val):\n",
    "            vis=[[False]*n for _ in range(m)]\n",
    "            def check(i,j,k):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    return True\n",
    "                vis[i][j]=True\n",
    "                for x,y in dirs:\n",
    "                    x=x+i\n",
    "                    y=y+j\n",
    "                    if not (0<=x<m and 0<=y<n) or vis[x][y]:\n",
    "                        continue\n",
    "                    if grid[x][y]>=k and check(x, y, k):\n",
    "                            return True\n",
    "                return False\n",
    "            return check(0, 0, val) \n",
    "                        \n",
    "        left = 0\n",
    "        right = min(grid[0][0], grid[-1][-1])\n",
    " \n",
    "        while left < right:\n",
    "            # 获取左边界和右边界之间的中间值。\n",
    "            middle = (left + right + 1) // 2\n",
    "\n",
    "            # 确认我们能否找到一条值为 middle 的路径，\n",
    "            # 并减半搜索空间。\n",
    "            if path_exists(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        \n",
    "        # 一旦左右边界重合，我们就找到目标值，\n",
    "        # 即路径的最大值。\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = min(grid[0][0], grid[-1][-1])\n",
    "        lst = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] < ans:\n",
    "                    lst.add(grid[i][j])\n",
    "        lst.add(ans)\n",
    "        lst = list(lst)\n",
    "        lst.sort()\n",
    "        def dfs(r=0, c=0):\n",
    "            if r == m - 1 and c == n - 1:\n",
    "                return True\n",
    "            visited[r][c] = 1\n",
    "            for x, y in [(r,c+1),(r+1,c),(r,c-1),(r-1,c)]:\n",
    "                if 0<=x<m and 0<=y<n and not visited[x][y] and grid[x][y] >= tmp:\n",
    "                    if dfs(x,y):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        left, right = 0, len(lst) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            tmp = lst[mid]\n",
    "            visited = [[0] * n for _ in range(m)]\n",
    "            if dfs():\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return lst[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = min(grid[0][0], grid[-1][-1])\n",
    "        lst = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] <= ans:\n",
    "                    lst.add(grid[i][j])\n",
    "        lst.add(ans)\n",
    "        lst = list(lst)\n",
    "        lst.sort()\n",
    "        def dfs(r=0, c=0):\n",
    "            if r == m - 1 and c == n - 1:\n",
    "                return True\n",
    "            visited[r][c] = 1\n",
    "            for x, y in [(r,c+1),(r+1,c),(r,c-1),(r-1,c)]:\n",
    "                if 0<=x<m and 0<=y<n and not visited[x][y] and grid[x][y] >= tmp:\n",
    "                    if dfs(x,y):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        left, right = 0, len(lst) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            tmp = lst[mid]\n",
    "            visited = [[0] * n for _ in range(m)]\n",
    "            if dfs():\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return lst[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumMinimumPath(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = min(grid[0][0], grid[-1][-1])\n",
    "        lst = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] <= ans:\n",
    "                    lst.add(grid[i][j])\n",
    "        lst.add(ans)\n",
    "        lst = list(lst)\n",
    "        lst.sort()\n",
    "        def dfs(r=0, c=0):\n",
    "            if r == m - 1 and c == n - 1:\n",
    "                return True\n",
    "            visited[r][c] = 1\n",
    "            for x, y in [(r,c+1),(r+1,c),(r,c-1),(r-1,c)]:\n",
    "                if 0<=x<m and 0<=y<n and not visited[x][y] and grid[x][y] >= tmp:\n",
    "                    if dfs(x,y):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        left, right = 0, len(lst) - 1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            tmp = lst[mid]\n",
    "            visited = [[0] * n for _ in range(m)]\n",
    "            if dfs():\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return lst[left]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
